package com.leetcode.LC_MED;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.Collections;
import java.util.List;

public class LC47 {
    public List<List<Integer>> permuteUnique(int[] nums) {

        ArrayList<List<Integer>> lists = new ArrayList<>();
        if (nums == null || nums.length == 0) {
            return lists;
        }
        Arrays.sort(nums);
        boolean[] booleans = new boolean[nums.length];
        Arrays.fill(booleans, true);
        bfs(nums, lists, new ArrayList<>(), 0, booleans);

        return lists;
    }

    private void bfs(int[] nums, List<List<Integer>> lists, List<Integer> list, int index, boolean[] booleans) {
        if (list.size() == nums.length) {
            lists.add(new ArrayList<>(list));
            return;
        }

        for (int i = index; i < nums.length; i++) {
            // 写 booleans[i - 1] 是因为 nums[i - 1] 在深度优先遍历的过程中刚刚被撤销选择
            //自己的理解是保证首个重复数已被使用
            if (i  > 0 && nums[i - 1] == nums[i]&& booleans[i - 1]) {
                continue;
            }
            if (booleans[i]) {
                list.add(nums[i]);
                booleans[i] = false;
                bfs(nums, lists, list, index, booleans);
                booleans[i] = true;
                list.remove(list.size() - 1);
            }
        }
    }

    public static void main(String[] args) {
        for (List<Integer> list : new LC47().permuteUnique(new int[]{1, 1, 3})) {
            for (Integer integer : list) {
                System.out.print(integer + " ");
            }
            System.out.println();
        }
    }
}
